1. Field of the Invention
The present invention relates to an apparatus and method for effectively performing a fixed point multiplication used in a transform algorithm such as a DCT (Discrete Cosine Transformal) in use for a multimedia codec. In particular, the invention is directed to a fixed point multiplying apparatus and method, which encodes a multiplicand into an independent binary system rather than a conventional binary system to use the encoded multiplicand in the transform algorithm, by which the multiplication is executed at a high speed with a simple structure and a small gate number.
2. Description of the Related Art
The Discrete Cosine Transform (DCT) is growing into a major element of the H.261, JPEG and MPEG as international multimedia standards at present due to the excellent performance of image compression.
Lossless compression completely restores a text, diagram, general data and the like, however, it has a mean compressibility of about 2 to 1. On the contrary, a compressibility of 10 to 1 or more can be easily obtained if the data such as an image, audio, sound and the like are so compressed to allow a small loss that cannot be detected by bare eyes or ears.
A multimedia image has a high repetitiveness among frames and pixels in one frame, and thus readily obtains a compressibility of 30 to 1 or more by utilizing visual characteristics as can be seen in an MPEG image compression. In a still image constituted of a single frame, only pixels in one frame are repeated while no repetition exists among frames. Therefore, the still image has a compressibility substantially lower than the MPEG as can be seen in the JPEG. The image such as a three-dimensional (multimedia) image or two-dimensional (still) image shows a high compressibility due to a high repetitiveness. On the contrary, an audio or sound is a one-dimensional data having repetitiveness lower than that of the image, and thus has a much lower compressibility. The Vector Sum Excited Linear Prediction (VSELP) as an audio compression scheme for a mobile communication in the North America obtains a compressibility of about 8 to 1. In the Dolby AC-3 or MPEG audio compression, the compressibility is about 6 to 1 in a single channel and 10 to 1 in a stereo or multi-channel (i.e. a 5.1 channel in watching a theatrical film) having a high repetitiveness among channels. In loss coding schemes, a transform coding is most widely used for effectively compressing the image data. A basic concept of this coding divides data, which are spatially arranged with a high correlation, into several frequency components ranging from a lower frequency component to a higher frequency component due to orthogonal transformation. Each of the frequency components is separately quantized.
The correlation substantially disappears among the frequency components, and the energy of a signal is concentrated to the lower frequency. Gain of the transform coding, which is obtained in the same bit rate as the simple Pulse Code Modulation (PCM), is the same as a ratio between the arithmetic mean and the geometric mean of the distribution of the frequency components. The compressibility increases as the energy is further concentrated toward the lower frequency.
The simple PCM about spatial data expresses all samples into bits of the same length, e.g. m-bit/sample, in which a signal-to-quantization noise ratio is about 6 m. On the contrary, in the data converted into a frequency range through the orthogonal transformation, more bits are allocated to such a frequency component which accumulates more energy (i.e., has a large value of distribution) so as to more completely express the frequency component. Every one bit is further allocated whenever the distribution is quadrupled (i.e. the amplitude is doubled) so that all of the frequency components have the same quantization error characteristics.
In various orthogonal transforms, the Karhunen-Loeve Transform (KLT) shows the most excellent compression effect due to the most theoretically excellent energy concentration characteristics. However, KLT cannot be used in practice because a conversion function is necessarily defined again for each image. In the DCT which is growing into the major technique in several international standards at present, 8×8 sized pixels are bound into one block as a unit of transformation. Enlarging the block increases the compressibility while barely realizing the transformation. The 8×8 block is experimentally selected as the compromise between performance and easiness of realization.
Quantization of the DCT may include Scalar Quantization (SQ) and Vector Quantization (VQ). The VQ is effective when the correlation among coefficients is high, but has a complexity higher than the SQ. Since the DCT coefficients have substantially no correlation, the SQ is adopted as the international standard at present. Further, the SQ also is divided into a linear scheme which is readily realized and a non-linear scheme which has excellent characteristics. The performance difference between the two schemes is narrowed when the quantized coefficients undergo entropy encoding (lossless) again. The H.261, JPEG and MPEG-1 use the linear scheme only because the entropy encoding is accompanied in the present international standard. However, the MPEG-2 adopts the non-linear scheme also for performance improvement.
Further, for the purpose of carrying out a lossless compression using statistical characteristics of the quantized DCT coefficients, the international standard combines the Run-length Encoding with the Huffman Encoding. The image compression is carried out via combination of various techniques such as the DCT, quantization, Run-length Encoding, Huffman Encoding and movement compensating DPCM (corresponding to the multimedia image only).
The transform algorithm such as the DCT used in the multimedia codec uses the multiplication with fixed points at least once. However, the real time image compression, for example, generally uses a fixed point operation in executing such a multiplication with a hardware because of constraining conditions including velocity and number of gate in use. In such a fixed point operation, however, a 2n bit operation result occurs in an n bit operation so that the delay time of a parallel adder causes a disadvantage to a high-speed operation.